The invention relates to image storage and processing in computers, and more specifically relates to storing and processing images of arbitrary 2-dimensional shapes in a graphics system that supports anti-aliasing.
Most modern computer graphics systems today use raster graphics to display images. A raster graphics system displays an image as a raster grid, where each line of the grid is composed of a row of pixels. The image may be stored as a 2-dimensional array of values, where each row of the array corresponds to a grid line of pixels, and each value of the array represents the data associated with a particular pixel. The image can then be processed via the array, and converted back into scan lines for display on the raster grid. As the capability of graphics systems increase, more complex images are created, with a corresponding increase in the complexity of storing and processing those images.
Most operating systems, therefore, have specially designed graphics subsystems that have been developed to address the problems inherent in creating, manipulating (define, clip, fill, draw and combine), and storing images as files in computer memory. For example, in the Microsoft Windows- operating systems, the subsystem that controls the display of text and graphics is called the Graphics Device Interface (GDI). GDI functionality is provided through an application programming interface (API) that includes functions to create graphical objects and manipulate those objects in memory. GDI draws lines, curves, closed figures, text, and bitmapped images on display devices and printers. There are a number of methods that have been developed in GDI and in other graphics subsystems for manipulating complex images. None, however, have all of the desirable characteristics of a method for storing and processing images of arbitrary 2-dimensional shapes, including compact storage requirements, scan-conversion efficiency and support for anti-aliasing.
Compact storage of the image is desirable since images of arbitrary 2-dimensional shapes tend to be very large collections of data. One way to represent an image of an arbitrary 2-dimensional shape in memory is with a binary mask, which is a 2-dimensional array of binary values that simply indicate the presence or absence of the shape. This type of representation requires a relatively small amount of memory by today""s standards (only 128,000 bytes with a resolution of 1024xc3x971024 pixels). For anti-aliased images, however, the data representing an image of an arbitrary 2-dimensional shape is more complex, requiring non-binary values to be stored for each pixel. These non-binary values represent the opacity of the pixel, and are referred to as alpha values. Storing alpha values requires significantly more bits per pixel to accurately represent the image in memory.
Scan-conversion efficiency is desirable since scan-conversion of an image stored in memory is computationally intensive. Moreover, every time an image is moved or re-sized on the drawing surface, the entire primitive comprising the image must be scan-converted anew.
Lastly, support for anti-aliasing is desirable because most graphics subsystems today employ anti-aliasing techniques. Aliasing results in the appearance of xe2x80x9cjaggiesxe2x80x9d or xe2x80x9cstaircasingxe2x80x9d, usually at the edges of the primitives of the image. These undesirable characteristics are common because most shapes can only be approximated with pixels on the raster grid. Although the use of anti-aliasing techniques improves the appearance of the image, it does so by altering the opacity of pixels at the image""s boundaries. The alpha values associated with those pixels can range from fully transparent to fully opaque. A fully transparent pixel is represented by a value of 0, whereas a fully opaque pixel may be represented by a value of 255 for 8-bit alpha values, or, more generally, by a value of 2nxe2x88x921 for n-bit alpha values. A range of alpha values may even be represented as floating values between 0 and 1. A semi-transparent pixel is represented by those values in between. The presence of a range of alpha values associated with the image not only increases the image""s complexity, but makes it more difficult to process using existing methodology.
For example, one method of storing image data that is well-known in the art is run-length encoding. As described in Foley, et al., Computer Graphics Principles and Practice, Second Edition, run-length encoding is used for images having a great deal of repetition. It consists of encoding a count of the number of contiguous pixels having the same value, and the value itself. One example of an improvement on this basic idea is the assignment of a negative count to indicate that n-pixels"" worth of unencoded data follow.
Another method of storing image data is to use a Region. A Region is a graphical object that subdivides an arbitrary 2-dimensional shape into a series of rectangular areas. The notion of a Region was developed for the graphics subsystems in the Macintosh and Microsoft Windowso operating systems to more easily store and process arbitrary 2-dimensional shapes.
An example of a prior art Region (150) is illustrated in FIG. 1. Since a Region was originally designed to accommodate only shapes displayed as simple opaque images, the image data structure of Region is based on an image of an arbitrary 2-dimensional shape expressed as a grid of binary values, e.g. 0 and 1, where the value 0 represents a transparent pixel (absence of the shape), and the 25 value 1 represents an opaque pixel (presence of the shape). In the example shown in FIG. 1, an arbitrary 2-dimensional shape is subdivided into an 8xc3x978 grid of pixels (110). Instead of using a 2-dimensional array to literally store the value of each pixel, or using run-length encoding to store the counts and values of the pixels, a Region stores the image data according to the rectangular coordinates of the shape on the grid (110). The rectangular coordinates consist of the number of rows, e.g. Y1, Y2, etc. (120), having identical patterns of Is and Os in the x-direction, the start and stop locations of those patterns in the x-direction, e.g. X1, X2, etc. (130) and the height of the rows having identical patterns, e.g. H1, H2, etc (140) (where height is equal to the number of rows). Thus, a great deal of the redundancy in storing the image is eliminated, and enables a Region (150) to store an arbitrary 2-dimensional shape in a more compact form. A Region also provides for efficient scan-conversion of the stored image.
A major drawback to using a Region, however, is the inability to store and process images having non-binary values associated with the pixels of the image. For example, anti-aliased images typically have non-binary alpha values associated with the pixels at the edges of the arbitrary shape. These non-binary alpha values represent the semi-transparent pixels in the boundaries between the fully transparent and opaque areas present in anti-aliased images. But a Region can only store the fully opaque and fully transparent areas. Thus, the structure of a Region makes it incapable of storing the semi-transparent areas. Moreover, the proper functioning of the combination operations provided for Regions depend upon limiting the representation of a shape to only fully opaque or fully transparent areas. Thus, the combination operations provided for Regions are unavailable for use with anti-aliased images.
As graphics subsystems advance, support for anti-aliased images is critical. Hence, a new approach to storing and processing images is desirable, but without sacrificing the compactness in storage requirements or the efficiency in scan-conversion rates achieved by using a Region.
The invention provides an improved method for storing and processing images of arbitrary 2-dimensional shapes in a graphics subsystem that supports anti-aliasing. The method employs a novel graphics object implemented as an AlphaRegion. The data in an AlphaRegion is stored in an alpha image data structure that is capable of representing an anti-aliased image of an arbitrary 2-dimensional shape in a manner not possible using existing structures such as the Region""s image data structure. While the method is implemented in software program modules, it can also be implemented in digital hardware logic or in a combination of hardware and software components.
In the implementation, an AlphaRegion defines an arbitrary 2-dimensional shape as a series of rectangular areas. Instead of storing the rectangular coordinates of the areas, an AlphaRegion stores the information according to the y-bands. A y-band represents a set of contiguous rows of pixels within a rectangular area that all have the same pattern of opacity levels in the x-direction, identified in an AlphaRegion as an x-pattern.
In an alternative implementation, an AlphaRegion can store the information according to the x-bands, where an x-band represents a set of contiguous columns of pixels within a rectangular area that all have the same pattern of opacity levels in the y-direction, identified in an AlphaRegion as a y-pattern. For simplicity, an AlphaRegion is described in terms of storing the information horizontally only, according to the y-bands. However, storage of the information by vertically decomposing an AlphaRegion into columns instead of rows would work equally well.
Either way, completely transparent rows or columns, as the case may be, are considered outside of an AlphaRegion and are not recorded. Each x-pattern of the rows (or y-pattern of the columns), that are recorded is classified as opaque, transparent, or semi-transparent according to the alpha values appearing in the x-pattern. Furthermore, the alpha values of only the first occurrence of a recurring x-pattern (or y-pattern) is recorded.
Each span of purely opaque or purely semi-transparent pixels appearing within an x-pattern is recorded according to its starting location and width, and is identified in AlphaRegion as an x-span. The alpha values of only the semi-transparent x-spans within a particular x-pattern are recorded; the opaque x-spans are simply assumed as the default value. In this way, AlphaRegion eliminates as much redundancy in the recorded data as possible. Once recorded, the data in an AlphaRegion is easily used to reconstruct the shape for scan-conversion and display. More importantly, since the alpha values are stored in the AlphaRegion itself, the compressed AlphaRegion data may be used directly in graphical operations to combine or render the shapes without reference to separately stored alpha values.
The method of the invention implements numerous functions to construct AlphaRegion""s alpha image data structure from a variety of image data sources. For example, an AlphaRegion""s alpha image data structure may be created directly from various primitive shapes including a rectangle, ellipse, polygon, or path, using the methods supplied in the AlphaRegion class itself. Another implementation constructs an AlphaRegion""s alpha image data structure from a previously encoded super-sampled conventional 1-bit Region or from a super-sampled bitmap. The alpha values for each of these images is derived by the method of constructing the AlphaRegion. Alternatively, in yet another implementation, an AlphaRegion""s alpha image data structure can also be constructed from an alpha-mask, where an alpha-mask is a literal representation of the alpha values associated with an image of an arbitrary 2-dimensional shape stored in memory. In this implementation, the alpha values are contained in the image data source itself. Therefore, this type of an AlphaRegion can essentially be used as a compact form of an alpha-mask.
AlphaRegions can potentially be constructed via other means as well. For example, an AlphaRegion could be constructed directly from a scan-line conversion of a geometric shape. Regardless of the method of construction, an implementation of an AlphaRegion records information about the shape into a compact form by structuring the alpha image data into three arrays. The first array, yInfo, contains the data representing the number and location of the y-bands, the second array, xInfo, contains the data representing the number and location of the x-patterns, and the third array, alphaData, contains the data representing the alpha values of the semi-transparent x-spans in the x-patterns.
The methods of AlphaRegion employ techniques to construct an optimized representation of a given image. Thus, implementations of the methods may include variations in representing the data depending upon the characteristics of the image. For example, an image may have an x-pattern with a single opaque pixel surrounded by semi-transparent pixels. In that case, the implementation of the method of AlphaRegion combines the opaque single-pixel x-span with the surrounding semi-transparent x-spans to create one semi-transparent x-span. The combination of x-spans will increase efficiency both in the use of memory and in the performance of graphical operations, such as filling. In an alternative implementation, the creator of a particular instance of an AlphaRegion may dictate the definition, taking into consideration the characteristics of the image being represented.
The method of the invention not only stores the anti-aliased image data in the AlphaRegion""s alpha image data structure, but implements numerous functions to process an AlphaRegion, including functions to combine two AlphaRegions, and to clip, fill or render an AlphaRegion on the drawing surface. For example, once constructed, a shape represented in an AlphaRegion""s alpha image data structure may be rendered by performing a filling method on the AlphaRegion to recreate the shape on the drawing surface. Two AlphaRegions representing different shapes may be combined using one of the combination operators AND, OR, XOR, SUBTRACT and SUBTRACT_FROM. Moreover, shapes constructed in an AlphaRegion are capable of being used in clipping, masking and source-over drawing operations. An AlphaRegion is implemented as a class object with methods for constructing and deconstructing, recording, rendering and combining the objects.
The method implements image storage and processing most efficiently for images that are relatively flat, with small anti-aliased boundaries. Since not all images will be flat, implementations of the method may include other features to increase the flexibility of the application of an AlphaRegion. For example, a particular image may have an overall gradient of opacity levels resulting in a large number of semi-transparent pixels evenly distributed throughout the y-bands of an AlphaRegion, and not just in the boundary area. In that case, the memory savings resulting from the implementation of AlphaRegion may be negligible, and the alpha mask may be used instead. Thus, one feature of the invention is to be able to selectively apply an AlphaRegion so as to optimize its use in conjunction with other recognized methods of storing and manipulating images.
Further advantages and features of the invention will become apparent in the following detailed description and accompanying drawings.